class OffsetRange {
    /**
     * A range of offsets (0-based).
     * 左闭右开
     */
    constructor(start, end) {
        this.start = start
        this.end = end
    }

    intersect(other) {
        const L = Math.max(this.start, other.start)
        const R = Math.min(this.end, other.end)

        if (L < R) {
            return new OffsetRange(L, R)
        }

        if (this.start === this.end) {
            if (other.start < this.start && this.start < other.end) {
                return new OffsetRange(this.start, this.end)
            }
        }

        if (other.start === other.end) {
            if (this.start < other.start && other.start < this.end) {
                return new OffsetRange(other.start, other.end)
            }
        }

        return null
    }

    equals(other) {
        return this.start === other.start && this.end === other.end
    }

    get length() {
        return this.end - this.start
    }
}

class SequenceDiff {
    constructor(seq1Range, seq2Range) {
        this.seq1Range = seq1Range
        this.seq2Range = seq2Range
    }

    toJSON() {
        return {
            seq1Range: {
                start: this.seq1Range.start,
                end: this.seq1Range.end,
            },
            seq2Range: {
                start: this.seq2Range.start,
                end: this.seq2Range.end,
            },
        }
    }

    toString() {
        return `SequenceDiff(${this.seq1Range.start}, ${this.seq1Range.end}, ${this.seq2Range.start}, ${this.seq2Range.end})`
    }
}

function process_before_compute(input) {
    if (typeof input === 'string') {
        if (input === '') input = []
        else input = input.trim().split('\n')
    }
    return input
}

function list2str(list) {
    if (list.length === 0) return ''
    return list.join('\n') + '\n'
}

function compute(
    sequence1,
    sequence2,
    equalityScore = (x, y) => (x === y ? 1 : 0),
) {
    sequence1 = process_before_compute(sequence1)
    sequence2 = process_before_compute(sequence2)
    console.log('sequence1:', sequence1)
    console.log('sequence2:', sequence2)
    if (sequence1.length === 0 || sequence2.length === 0) {
        return [
            new SequenceDiff(
                new OffsetRange(0, sequence1.length),
                new OffsetRange(0, sequence2.length),
            ),
        ]
    }

    const lcsLengths = Array.from({ length: sequence1.length }, () =>
        Array(sequence2.length).fill(0),
    )
    const directions = Array.from({ length: sequence1.length }, () =>
        Array(sequence2.length).fill(0),
    )
    const lengths = Array.from({ length: sequence1.length }, () =>
        Array(sequence2.length).fill(0),
    )

    for (let s1 = 0; s1 < sequence1.length; s1++) {
        for (let s2 = 0; s2 < sequence2.length; s2++) {
            const horizontalLen = s1 === 0 ? 0 : lcsLengths[s1 - 1][s2]
            const verticalLen = s2 === 0 ? 0 : lcsLengths[s1][s2 - 1]

            let extendedSeqScore = -1
            if (sequence1[s1] === sequence2[s2]) {
                extendedSeqScore =
                    (s1 === 0 || s2 === 0 ? 0 : lcsLengths[s1 - 1][s2 - 1]) +
                    equalityScore(sequence1[s1], sequence2[s2])

                if (s1 > 0 && s2 > 0 && directions[s1 - 1][s2 - 1] === 3) {
                    extendedSeqScore += lengths[s1 - 1][s2 - 1]
                }
            }

            const newValue = Math.max(
                horizontalLen,
                verticalLen,
                extendedSeqScore,
            )

            if (newValue === extendedSeqScore) {
                lengths[s1][s2] =
                    (s1 > 0 && s2 > 0 ? lengths[s1 - 1][s2 - 1] : 0) + 1
                directions[s1][s2] = 3
            } else if (newValue === horizontalLen) {
                lengths[s1][s2] = 0
                directions[s1][s2] = 1
            } else if (newValue === verticalLen) {
                lengths[s1][s2] = 0
                directions[s1][s2] = 2
            }

            lcsLengths[s1][s2] = newValue
        }
    }

    const result = []
    let lastAligningPosS1 = sequence1.length
    let lastAligningPosS2 = sequence2.length

    const reportDecreasingAligningPositions = (s1, s2) => {
        if (s1 + 1 !== lastAligningPosS1 || s2 + 1 !== lastAligningPosS2) {
            result.push(
                new SequenceDiff(
                    new OffsetRange(s1 + 1, lastAligningPosS1),
                    new OffsetRange(s2 + 1, lastAligningPosS2),
                ),
            )
        }
        lastAligningPosS1 = s1
        lastAligningPosS2 = s2
    }

    let s1 = sequence1.length - 1
    let s2 = sequence2.length - 1

    while (s1 >= 0 && s2 >= 0) {
        if (directions[s1][s2] === 3) {
            reportDecreasingAligningPositions(s1, s2)
            s1--
            s2--
        } else if (directions[s1][s2] === 1) {
            s1--
        } else {
            s2--
        }
    }

    reportDecreasingAligningPositions(-1, -1)
    result.reverse()

    return result
}

export default compute
export { OffsetRange, SequenceDiff, process_before_compute, list2str }
